package offerbook;

import java.util.Arrays;

/**
 * Created at 2019/11/1 0001 下午 8:34
 * 题目：有n个筛子，同时投放，求n个筛子的和出现的概率。
 * 分析：n个筛子的sum->[n,6*n],n个筛子摇出的可能的结果6^n
 *
 * 输入: 1
 * 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
 *
 * 方式1：暴力回溯。
 * 第n个筛子和为sum下的种数，依赖于第 n-1个筛子和为 sum - i, 1<=i<=6
 * 注意basecase：
 * n = 1时 ， 1<=sum <= 6 返回1，其他返回0
 * n = sum时，直接返回1
 * n > sum时，返回0
 * 其他则遍历
 * 方式2：记忆性回溯
 * memo[i][j]表示前i颗筛子，和为j下的总次数
 *
 * 方式3:动态规划
 * 设筛子数n和总和s为函数f(n,s)
 * 第n次筛子和为s的情况 = 第n-1次筛子和为s-1,s-2,.....,s-6的情况
 * f(n,s) = f(n-1,s-1)+f(n-1,s-2)+...+f(n-1,s-6)
 *
 */
public class Code43_筛子数和 {
    //常量要这样定义，方便代码的维护
    private static final int GLOBAL_VALUE = 6;

    /**
     * 方式1：递归
     */
    public static double[] getPro1(int n) {
        //sum最小是 n，最大是 6n ,所以总共是5n+1总情况
        double[] res = new double[5*n+1];
        int index = 0;
        for(int sum = n; sum <= 6*n; sum++){
            res[index++] = GetSum(n, sum)/Math.pow(6,n);
        }
        return res;
    }
    /**
     * 统计出现的次数
     * @param n  投掷n个筛子
     * @param sum  在n个筛子情况下和为sum的情况
     * @return  出现的次数
     */
    private static int GetSum(int n, int sum) {
        //n =1时，当 1 <= s <=6,都会出现1次
        if (n == 1){//临界状态1，只有一个骰子
            return (sum >=1 && sum <= 6) ? 1 : 0;
        }
        // sum最小是n
        if (sum <= n){//临界状态2，n个骰子最小s=n
            return sum == n ? 1 : 0;
        }
        int totalSum = 0;
        //对于n颗筛子，求n-1颗筛子的sum情况，考虑 1-6情况，也就是sum-i (0<=i<=6)
        //n-1颗筛子的和i最小是 n-1,最大是 6*(n-1)
//        for (int i = n-1; i <= 6*(n-1); i++) {
        for (int i = 1; i <= 6; i++) {
            //当前sum - i
            totalSum += GetSum(n - 1, sum-i);
        }
        return totalSum;
    }
    /**
     * 方式2：记忆性回溯
     */
    public static double[] getPro2(int n) {
        //sum最小是 n，最大是 6n ,所以总共是5n+1总情况
        double[] res = new double[5*n+1];
        int index = 0;
        //memo[n][sum]表示前n颗筛子和为sum的种数
        int [][]memo = new int[n+1][6*n+1];
        for (int[] ints : memo) {
            Arrays.fill(ints,-1);
        }
        for(int sum = n; sum <= 6*n; sum++){
            res[index++] = GetSum(n, sum,memo)/Math.pow(6,n);
        }
        return res;
    }

    private static double GetSum(int n, int sum, int[][] memo) {
        //n =1时，当 1 <= s <=6,都会出现1次
        if (n == 1){//临界状态1，只有一个骰子
            return (sum >=1 && sum <= 6) ? 1 : 0;
        }
        // sum最小是n
        if (sum <= n){//临界状态2，n个骰子最小s=n
            return sum == n ? 1 : 0;
        }

        if(memo[n][sum] != - 1) return memo[n][sum];
        int totalSum = 0;
        //对于n颗筛子，求n-1颗筛子的sum情况，考虑 1-6情况，也就是sum-i (0<=i<=6)
        //n-1颗筛子的和i最小是 n-1,最大是 6*(n-1)
//        for (int i = n-1; i <= 6*(n-1); i++) {
        for (int i = 1; i <= 6; i++) {
            //当前sum - i
            totalSum += GetSum(n - 1, sum-i,memo);
        }
        return memo[n][sum] = totalSum;
    }

    /**
     * 方式3:dp
     * 开辟两个长度为6*n+1的数组，第一个存上一次的和，第二个存下一次的和。然后复用。
     * 利用两个数组间的和的位置关系，完成DP。f(n,s) = f(n-1,s-1)+f(n-1,s-2)+...+f(n-1,s-6)
     */
    public static void getPro3(int n) {
        if (n <= 0) {
            return;
        }
        //n个筛子，和最大是 6*n,存储0-6*n+1。下标代表sum,值1或0.1代表出现过
        int[][] pProbabilities = new int[2][GLOBAL_VALUE * n + 1];
        //轮询数组
        int pollFlag = 0;
        //当第一次抛掷骰子时，有6种可能，每种可能出现一次
        for (int i = 1; i <= GLOBAL_VALUE; i++) {
            pProbabilities[pollFlag][i] = 1;
        }
        //从第二次开始掷骰子，假设第一个数组中的第n个数字表示骰子和为n出现的次数，
        //在下一循环中，我们加上一个新骰子，
        //此时和为n的骰子出现次数应该等于上一次循环中骰子点数和为n-1,n-2,n-3,n-4,n-5，n-6的次数总和
        //所以我们把另一个数组的第n个数字设为前一个数组对应的n-1,n-2,n-3,n-4,n-5，n-6之和
        for (int count = 2; count <= n; count++) {
            //第count次扔筛子，和最小为count，所以0~count-1为0
            for (int i = 0; i < count; i++) {
                pProbabilities[1 - pollFlag][i] = 0;
            }
            //第count次掷骰子，和最小为count，最大为g_maxValue*count，所以更新count - 6 *count位置的元素
            for (int i = count; i <= GLOBAL_VALUE * count; i++) {
                pProbabilities[1 - pollFlag][i] = 0;
                //利用DP公式求和,注意边界 j<=i ,因为用到p[pollFlag][i-j]

                //假设 count <=6 ，也就是第count次扔筛子，那么 p[1][count]代表和为count <=6的情况，
                // 只可能是上次和为1 ~count-1产生的，所以要考虑 j<=i。
                //当count >6,那么肯定是上次投出的1-6的次数的和
                for (int j = 1; j <= i && j <= GLOBAL_VALUE; j++) {
                    pProbabilities[1 - pollFlag][i] += pProbabilities[pollFlag][i - j];
                }
            }
            //交换两个数组的位置，复用
            pollFlag = 1 - pollFlag;
        }
        double totalSum = Math.pow(GLOBAL_VALUE, n);
        for (int i = n; i <= GLOBAL_VALUE * n; i++) {
            double ratio = pProbabilities[pollFlag][i] / totalSum;
            System.out.println("sum: " + i + " ratio: " + ratio);
        }
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        //getProbability2_2(100); // 60ms
        System.out.println(Arrays.toString(getPro2(3)));
        System.out.println("用时:" + (System.currentTimeMillis() - start));
    }
}
